package com.example.hashtable;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度
 * <p>
 * 输入: "eceba"
 * 输出: 3
 * 解释: t 是 "ece"，长度为3。
 * <p>
 * 输入: "ccaabbb"
 * 输出: 5
 * 解释: t 是 "aabbb"，长度为5。
 */
public class Leetcode159_LengthOfLongestSubstringTwoDistinct {

    public static void main(String[] args) {
//        System.out.println(lengthOfLongestSubstringTwoDistinct("eceba"));
        System.out.println(isStrGreatTwoChar("eceb"));

    }

    /**
     * 暴力法
     * 1.双指针截取字符串left、right
     * 2.判断子字符串是否由两个以上不重复的字符组成
     * 是 right右移 更新结果
     * 否 left右移
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstringTwoDistinct1(String s) {
        int len;
        if ((len = s.length()) < 3) {
            return len;
        }
        int maxSubStrLen = 0;
        int left = 0, right = 1;

        while (right < len) {
            if (isStrGreatTwoChar(s.substring(left, right + 1))) {
                left++;
            } else {
                int tmp = right - left + 1;
                maxSubStrLen = tmp > maxSubStrLen ? tmp : maxSubStrLen;
                right++;
            }
        }
        return maxSubStrLen;
    }

    /**
     * 解法一：和上一个题目类似，也可以采用滑动窗口的算法思想，选取left-right子串进行验证
     * 如果字符数量没有超过2，则记录此时的最大长度，并且right++
     * 如果字符数量超过2，则left++
     * 使用map存放出现过的字符及次数
     *
     * （优化算法，使用数组替代map)
     */
    public int lengthOfLongestSubstringTwoDistinct2(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        int count = 0;//不同的字符数量
        int maxLength = 0;
        while (right < len) {
            //在map中获取该字符出现的次数(不存在则为0),次数+1
            int rightNumber = map.getOrDefault(chars[right], 0) + 1;
            map.put(chars[right], rightNumber);//更新map
            if (rightNumber == 1) {//第一次出现
                count++;
            }
            right++;
            if (count <= 2) {
                maxLength = Math.max(maxLength, right - left);
            }
            while (count > 2) {
                //左侧移除一个字符，在map中获取该字符出现的次数-1
                int leftNumber = map.get(chars[left]) - 1;
                map.put(chars[left], leftNumber);//更新map
                if (leftNumber == 0) {
                    count--;
                }
                left++;
            }
        }
        return maxLength;
    }

    /**
     * 解法二 最优解
     * 改进1：考虑ASCII码表中的128个字符，可以使用数组代替map，存放每个字符出现的次数
     * 改进2：滑动窗口 只会扩大或者平移（我们要取的就是最大窗口长度）
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstringTwoDistinct3(String s) {
        final int length = s.length();
        final int[] map = new int[128];
        int right = 0, left = 0;
        //count 为不同字符的数量
        for (int count = 0; right < length; ) {
            //右侧新字符进入窗口
            if (map[s.charAt(right++)]++ == 0) {
                count++;
            }
            //如果新字符进入窗口后使得 不同字符数量大于2，则左侧窗口也向右滑动一个（窗口平移）
            if (count > 2) {
                if (--map[s.charAt(left++)] == 0) {
                    count--;
                }
            }
        }
        return right - left;
    }

    private static boolean isStrGreatTwoChar(String str) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            if (map.keySet().size() > 2) {
                return true;
            } else {
                if (!map.containsKey(str.charAt(i))) {
                    map.put(str.charAt(i), 1);
                }
            }
        }
        return map.keySet().size() > 2;
    }

}
